#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_SIZE 8 // 最大元素数量

// 并查集结构
typedef struct
{
    int parent[MAX_SIZE];     // 父结点数组
    int rank[MAX_SIZE];       // 秩数组（用于按秩合并）
    char *elements[MAX_SIZE]; // 元素名称数组
    int size;                 // 当前元素数量
} UnionFind;

// 1. 创建并查集
UnionFind *createUnionFind(char *items[], int count)
{
    if (count > MAX_SIZE)
    {
        printf("Error: Exceeded maximum size\n");
        return NULL;
    }

    UnionFind *uf = (UnionFind *)malloc(sizeof(UnionFind));
    uf->size = count;

    // 初始化元素名称
    for (int i = 0; i < count; i++)
    {
        uf->elements[i] = strdup(items[i]);
    }

    // 初始化父结点和秩
    for (int i = 0; i < count; i++)
    {
        uf->parent[i] = i; // 每个元素初始时是自己的父结点
        uf->rank[i] = 0;   // 初始秩为0
    }

    return uf;
}

// 2. 销毁并查集
void destroyUnionFind(UnionFind *uf)
{
    if (!uf)
        return;

    // 释放元素名称
    for (int i = 0; i < uf->size; i++)
    {
        free(uf->elements[i]);
    }

    // 释放并查集结构
    free(uf);
}

// 3. 查找操作（带路径压缩）
int find(UnionFind *uf, int x)
{
    if (uf->parent[x] != x)
    {
        uf->parent[x] = find(uf, uf->parent[x]); // 路径压缩
    }
    return uf->parent[x];
}

// 4. 合并操作（按秩合并）
void unionSets(UnionFind *uf, int x, int y)
{
    int rootX = find(uf, x);
    int rootY = find(uf, y);

    if (rootX == rootY)
        return; // 已在同一集合

    // 按秩合并
    if (uf->rank[rootX] < uf->rank[rootY])
    {
        uf->parent[rootX] = rootY;
    }
    else if (uf->rank[rootX] > uf->rank[rootY])
    {
        uf->parent[rootY] = rootX;
    }
    else
    {
        uf->parent[rootY] = rootX;
        uf->rank[rootX]++;
    }
}

// 5. 查找元素索引
int findIndex(UnionFind *uf, const char *item)
{
    for (int i = 0; i < uf->size; i++)
    {
        if (strcmp(uf->elements[i], item) == 0)
        {
            return i;
        }
    }
    return -1; // 未找到
}

// 6. 打印当前集合状态
void printSets(UnionFind *uf)
{
    printf("Current sets:\n");
    printf("Index | Element  | Parent | Root\n");
    printf("------|----------|--------|------\n");

    for (int i = 0; i < uf->size; i++)
    {
        int root = find(uf, i);
        printf("%-5d | %-8s | %-6d | %d\n",
               i, uf->elements[i], uf->parent[i], root);
    }
    printf("\n");
}

// 7. 按集合分组打印
void printGroupedSets(UnionFind *uf)
{
    printf("Grouped sets:\n");

    // 找出所有根结点
    int roots[MAX_SIZE] = {0};
    int rootCount = 0;

    for (int i = 0; i < uf->size; i++)
    {
        int root = find(uf, i);
        int found = 0;

        for (int j = 0; j < rootCount; j++)
        {
            if (roots[j] == root)
            {
                found = 1;
                break;
            }
        }

        if (!found)
        {
            roots[rootCount++] = root;
        }
    }

    // 打印每个集合
    for (int i = 0; i < rootCount; i++)
    {
        int root = roots[i];
        printf("Set %d (root: %s): ", i + 1, uf->elements[root]);

        for (int j = 0; j < uf->size; j++)
        {
            if (find(uf, j) == root)
            {
                printf("%s ", uf->elements[j]);
            }
        }
        printf("\n");
    }
    printf("\n");
}

int main()
{
    // 初始元素集合
    char *items[MAX_SIZE] = {
        "榴莲", "苹果", "香蕉", "葡萄",
        "青菜", "白菜", "青椒", "土豆"};

    // 1. 创建并查集
    UnionFind *uf = createUnionFind(items, MAX_SIZE);
    printf("Created Union-Find structure\n");

    // 初始状态：水果(0-3)和蔬菜(4-7)各自独立
    printSets(uf);
    printGroupedSets(uf);

    // 2. 合并水果和蔬菜内部
    // 合并水果：苹果和香蕉合并
    unionSets(uf, findIndex(uf, "苹果"), findIndex(uf, "香蕉"));
    printf("Merged 苹果 and 香蕉\n");

    // 合并蔬菜：青菜和白菜合并
    unionSets(uf, findIndex(uf, "青菜"), findIndex(uf, "白菜"));
    printf("Merged 青菜 and 白菜\n");

    printGroupedSets(uf);

    // 3. 进一步合并
    // 合并水果：榴莲和苹果合并（通过苹果连接到香蕉）
    unionSets(uf, findIndex(uf, "榴莲"), findIndex(uf, "苹果"));
    printf("Merged 榴莲 and 苹果\n");

    // 合并蔬菜：青椒和土豆合并
    unionSets(uf, findIndex(uf, "青椒"), findIndex(uf, "土豆"));
    printf("Merged 青椒 and 土豆\n");

    // 合并蔬菜：白菜和青椒合并（连接两个蔬菜集合）
    unionSets(uf, findIndex(uf, "白菜"), findIndex(uf, "青椒"));
    printf("Merged 白菜 and 青椒\n");

    printGroupedSets(uf);

    // 4. 查找操作演示
    int appleIndex = findIndex(uf, "苹果");
    int bananaIndex = findIndex(uf, "香蕉");
    printf("苹果 and 香蕉 in same set? %s\n",
           find(uf, appleIndex) == find(uf, bananaIndex) ? "Yes" : "No");

    int appleIndex2 = findIndex(uf, "苹果");
    int cabbageIndex = findIndex(uf, "白菜");
    printf("苹果 and 白菜 in same set? %s\n",
           find(uf, appleIndex2) == find(uf, cabbageIndex) ? "Yes" : "No");

    // 5. 销毁并查集
    destroyUnionFind(uf);
    printf("\nUnion-Find structure destroyed\n");

    return 0;
}